package main

import (
	"fmt"
	"leetcode"
	"math"
)

func main() {
	// [1,3,2,5,3,9]

	node6 := &leetcode.TreeNode{Val: 9, Left: nil, Right: nil}

	node5 := &leetcode.TreeNode{Val: 3, Left: nil, Right: nil}

	node4 := &leetcode.TreeNode{Val: 5, Left: nil, Right: nil}

	node3 := &leetcode.TreeNode{Val: 2, Left: nil, Right: node6}

	node2 := &leetcode.TreeNode{Val: 3, Left: node5, Right: node4}

	node1 := &leetcode.TreeNode{Val: 1, Left: node2, Right: node3}

	height := largestValues(node1)
	fmt.Println()
	fmt.Println(height)
}

func largestValues(root *leetcode.TreeNode) []int {
	values := make([]int, 0)
	if root == nil {
		return values
	}

	curRow := make([]*leetcode.TreeNode, 0)
	nextRow := make([]*leetcode.TreeNode, 0)
	curRow = append(curRow, root)
	for {
		if len(curRow) == 0 {
			break
		}
		maxValue := math.MinInt32
		for _, node := range curRow {
			if node.Val > maxValue {
				maxValue = node.Val
			}
			if node.Left != nil {
				nextRow = append(nextRow, node.Left)
			}
			if node.Right != nil {
				nextRow = append(nextRow, node.Right)
			}
		}
		values = append(values, maxValue)
		curRow = curRow[0:0]
		if len(nextRow) > 0 {
			curRow = make([]*leetcode.TreeNode, len(nextRow))
			copy(curRow, nextRow)
			nextRow = nextRow[0:0]
		}
	}
	return values
}
